Search results for "Sturmian word"

Sturmian words and overexponential codimension growth

2018

Abstract Let A be a non necessarily associative algebra over a field of characteristic zero satisfying a non-trivial polynomial identity. If A is a finite dimensional algebra or an associative algebra, it is known that the sequence c n ( A ) , n = 1 , 2 , … , of codimensions of A is exponentially bounded. If A is an infinite dimensional non associative algebra such sequence can have overexponential growth. Such phenomenon is present also in the case of Lie or Jordan algebras. In all known examples the smallest overexponential growth of c n ( A ) is ( n ! ) 1 2 . Here we construct a family of algebras whose codimension sequence grows like ( n ! ) α , for any real number α with 0 α 1 .

Burrows–Wheeler transform and Sturmian words

2003

A Characterization of Bispecial Sturmian Words

2012

A finite Sturmian word w over the alphabet {a,b} is left special (resp. right special) if aw and bw (resp. wa and wb) are both Sturmian words. A bispecial Sturmian word is a Sturmian word that is both left and right special. We show as a main result that bispecial Sturmian words are exactly the maximal internal factors of Christoffel words, that are words coding the digital approximations of segments in the Euclidean plane. This result is an extension of the known relation between central words and primitive Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the set of Sturmian wo…

STURMIAN WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES

1990

If x is a rational number, 0<x≤1, then A(x)c is a context-free language, where A(x) is the set of factors of the infinite Sturmian words with asymptotic density of 1’s smaller than or equal to x. We also prove a “gap” theorem i.e. A(x) can never be an unambiguous co-context-free language. The “gap” theorem is established by proving that the counting generating function of A(x) is transcendental. We show some links between Sturmian words, combinatorics and number theory.

Words and forbidden factors

2002

AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…

A Note on a Conjecture of Duval and Sturmian Words

2002

We prove a long standing conjecture of Duval in the special case of Sturmian words. Mathematics Subject Classication. ??????????????. Let U be a nonempty word on a nite alphabet A: A nonempty word B dierent from U is called a border of U if B is both a prex and sux of U: We say U is bordered if U admits a border, otherwise U is said to be unbordered. For example, U = 011001011 is bordered by the factor 011; while 00010001001 is unbordered. An integer 1 k n is a period of a word U = U1 :::U n if and only if for all 1 i n k we have Ui = Ui+k. It is easy to see that k is a period of U if and only if the prex B of U of length n k is a border of U or is empty. Let (U) denote the smallest period …

Characteristic Sturmian words are extremal for the Critical Factorization Theorem

2012

We prove that characteristic Sturmian words are extremal for the Critical Factorization Theorem (CFT) in the following sense. If p x ( n ) denotes the local period of an infinite word x at point n , we prove that x is a characteristic Sturmian word if and only if p x ( n ) is smaller than or equal to n + 1 for all n ≥ 1 and it is equal to n + 1 for infinitely many integers n . This result is extremal with respect to the \{CFT\} since a consequence of the \{CFT\} is that, for any infinite recurrent word x, either the function p x is bounded, and in such a case x is periodic, or p x ( n ) ≥ n + 1 for infinitely many integers n . As a byproduct of the techniques used in the paper we extend a r…

On Sturmian Graphs

2007

AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.

Hopcroft’s Algorithm and Cyclic Automata

2008

Minimization of deterministic finite automata is a largely studied problem of the Theory of Automata and Formal Languages. It consists in finding the unique (up to isomorphism) minimal deterministic automaton recognizing a set of words. The first approaches to this topic can be traced back to the 1950’s with the works of Huffman and Moore (cf. [12,15]). Over the years several methods to solve this problem have been proposed but the most efficient algorithm in the worst case was given by Hopcroft in [11]. Such an algorithm computes in O(n log n) the minimal automaton equivalent to a given automaton with n states. The Hopcroft’s algorithm has been widely studied, described and implemented by …

Fine and Wilf's Theorem for Three periods and a Generalization of Sturmian Words

1999

AbstractWe extend the theorem of Fine and Wilf to words having three periods. We then define the set 3-PER of words of maximal length for which such result does not apply. We prove that the set 3-PER and the sequences of complexity 2n + 1, introduced by Arnoux and Rauzy to generalize Sturmian words, have the same set of factors.